package class10;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 *
 * 图的宽度优先遍历&深度优先遍历
 *
 * 宽度优先遍历
 * 1.利用队列实现
 * 2.从源节点开始依次按照宽度进队列, 然后弹出
 * 3.每弹出一个点, 把该节点所有没有进过队列的邻接点放入队列
 * 4.直到队列变为空
 *
 * 深度优先遍历
 * 1.利用栈实现
 * 2.从源节点开始把节点按照深度放入栈,然后弹出
 * 3.每弹出一个点, 把该节点下一个没有进过栈的邻接点放入栈
 * 4.直到栈变空
 *
 */
public class Code02_BFS {

	// 从node出发，进行宽度优先遍历
	public static void bfs(Node node) {
		if (node == null) {
			return;
		}
		Queue<Node> queue = new LinkedList<>();
		//图需要set去重,避免出现环情况下,循环遍历(二叉树没有环, 所以二叉树宽度优先没有set)
		HashSet<Node> set = new HashSet<>();
		queue.add(node);
		set.add(node);
		while (!queue.isEmpty()) {
			//弹出则打印
			Node cur = queue.poll();
			System.out.println(cur.value);
			//所有直接邻居,不存在set中的就放入队列中
			for (Node next : cur.nexts) {
				if (!set.contains(next)) {
					set.add(next);
					queue.add(next);
				}
			}
		}
	}

}
